/* File: codrle3.c
   Author: David Bourgin
   Creation date: 1/2/94
   Last update: 22/9/94
   Purpose: Example of RLE type 3 encoding with a file source to compress.
*/

#include <stdio.h>
/* For routines printf,fputc,fread,fwrite and rewind */
#include <memory.h>
/* For routines memset,memcpy */
#include <stdlib.h>
/* For routine exit */

/* Error codes sent to the caller */
#define NO_ERROR      0
#define BAD_FILE_NAME 1
#define BAD_ARGUMENT  2

/* Useful constants */
#define FALSE 0
#define TRUE  1

#define MAX_FRAME_SIZE 256

/* Global variables */
FILE *source_file,*dest_file;

unsigned int index=0,
             buffer_read_size=0;
unsigned char buffer_read[768];

typedef struct { unsigned int array_size;
                 unsigned char *array_val;
               } t_tab;
#define ARRAY_SIZE(array)  ((array).array_size)
#define ARRAY_VAL(array)  ((array).array_val)
#define ARE_EQUAL(array1,array2)  ((ARRAY_SIZE(array1)==ARRAY_SIZE(array2))&&(!memcmp(ARRAY_VAL(array1),ARRAY_VAL(array2),ARRAY_SIZE(array1))))

/* Pseudo procedures */
#define size_remaing_to_read()  (buffer_read_size-index)
#define read_block()  { if (!size_remaing_to_read())\
                           { buffer_read_size=fread(buffer_read,1,sizeof(buffer_read),source_file);\
                             index=0;\
                           }\
                      }
#define move_index(i)  (index=(i))
#define beginning_of_data()  { (void)rewind(source_file); buffer_read_size=0; index=0; }
#define end_of_data()  (size_remaing_to_read()?FALSE:(index=0,!(buffer_read_size=fread(buffer_read,1,sizeof(buffer_read),source_file))))
#define read_byte()  ((unsigned char)(end_of_data()?EOF:buffer_read[index++]))
#define read_array(array,nb_to_read)  { ARRAY_SIZE(array)=(nb_to_read);\
                                        ARRAY_VAL(array)= &(buffer_read[index]);\
                                        index += (nb_to_read);\
                                      }
#define write_byte(x)  ((void)fputc((unsigned char)(x),dest_file))
#define write_array(array)  ((void)fwrite(ARRAY_VAL(array),1,ARRAY_SIZE(array),dest_file))
#define fill_block()  { (void)memcpy(buffer_read,&(buffer_read[index]),size_remaing_to_read());\
                        buffer_read_size=fread(&(buffer_read[size_remaing_to_read()]),1,sizeof(buffer_read)-size_remaing_to_read(),source_file)+size_remaing_to_read();\
                        index=0;\
                      }

void rle3look_for_occurr(basic_index,frame_nb,frame_size,
                         repetition_ok)
/* Returned parameters: 'frame_nb', 'frame_size' and 'repetition_ok' are modified
   Action: Looks in the byte buffer if there's a frame repetition from 'basic_index' position
   where size and repetition are respectively in 'frame_size' and 'frame_nb'.
   Whenever a repetition is met, 'repetition_ok' returns 'TRUE' otherwise 'repetition_ok' returns 'FALSE'
   Errors: Whenever there are no multiple frames then 'frame_nb' won't be modified
*/
unsigned int basic_index,*frame_nb,*frame_size;
int *repetition_ok;
{ int array_equality;
  t_tab array1,array2;

  *frame_size=1;
  *repetition_ok=FALSE;
  move_index(basic_index);
  while ((*frame_size<MAX_FRAME_SIZE)&&(size_remaing_to_read()>=(*frame_size << 1))&&(!*repetition_ok))
        { read_array(array1,*frame_size);
          read_array(array2,*frame_size);
          if (array_equality=ARE_EQUAL(array1,array2))
             { if (!basic_index)
                  { *frame_nb=2;
                    while ((size_remaing_to_read()>=*frame_size)&&(*frame_nb<=255)&&(array_equality))
                          { read_array(array1,*frame_size);
                            if (array_equality=ARE_EQUAL(array1,array2))
                               (*frame_nb)++;
                          }
                    (*frame_size)--;
                  }
               *repetition_ok=TRUE;
                             /* Specify to the caller there was a repetition */
             }
          (*frame_size)++;
          move_index(basic_index);
        }
}

void rle3write_non_rep(header_byte,non_repeated_byte)
/* Returned parameters: None
   Action: Writes in the output compression stream the byte 'non_repeated_byte'
   'header_byte' is used as marker as defined in RLE 3 method
   Errors: An input/output error could disturb the running of the program
*/
unsigned char header_byte,non_repeated_byte;
{ if (non_repeated_byte==header_byte)
     { write_byte(header_byte);
       write_byte(0);
       write_byte(0);
     }
  else write_byte(non_repeated_byte);
}

void rle3write_rep(header_byte,frame,frame_size,repetition)
/* Returned parameters: None
   Action: Writes in the output compression stream 'repetition' times 'frame' which size is given by 'frame_size'
   'header_byte' is used as marker as defined in RLE 3 method
   Errors: An input/output error could disturb the running of the program
*/
unsigned char header_byte;
t_tab frame;
unsigned int frame_size,repetition;
{ register unsigned int i,j;

  if ((repetition==1)&&(*ARRAY_VAL(frame)==header_byte))
     { write_byte(header_byte);
       write_byte(0);
       write_byte(repetition-1);
     }
  else if ((repetition-1)*frame_size>3)
          { write_byte(header_byte);
            write_byte(repetition-1);
            write_byte(frame_size-1);
            write_array(frame);
          }
       else for (i=1;i<=repetition;i++)
                for (j=0;j<frame_size;j++)
                    rle3write_non_rep(header_byte,ARRAY_VAL(frame)[j]);
}

void rle3encoding()
/* Returned parameters: None
   Action: Compresses with RLE type 3 method all bytes read by the function 'read_byte'
   Errors: An input/output error could disturb the running of the program
*/
{ register unsigned int i;
  unsigned long int occurrence_table[256];
  unsigned char header_byte;
  t_tab frame;
  unsigned int frame_nb1,frame_size1,frame_nb2,frame_size2;
  int repetition_valid;

  if (!end_of_data())        /* Is there at least a byte to analyze? */
     {                       /* Sets up the occurrence numbers of all bytes to 0 */
       (void)memset((char *)occurrence_table,0,sizeof(occurrence_table));
                             /* This is the same to fill 'occurrence_table' to 0.
                                It's fastest than to loop 256 times */
       while (!end_of_data())/* Valids the occurrences in 'occurrence_table' in regard to the data to compress */

             { header_byte=read_byte();
               occurrence_table[header_byte]++;
             }
       header_byte=0;
       for (i=1;i<=255;i++)
           if (occurrence_table[i]<occurrence_table[header_byte])
              header_byte=i;
       write_byte(header_byte);
       beginning_of_data();
       read_block();
       while (size_remaing_to_read())
             { rle3look_for_occurr(0,&frame_nb1,&frame_size1,&repetition_valid);
               if (repetition_valid)
                             /* Was there a repetition? */
                  { move_index((frame_nb1-1)*frame_size1);
                      read_array(frame,frame_size1);
                      rle3write_rep(header_byte,frame,frame_size1,frame_nb1);
                  }
               else {        /* No, then tests pattern repetition */
                      frame_size1=0;
                      do {   /* Tests sequences such as  5,2,3,2,3 */
                           frame_size1++;
                           rle3look_for_occurr(frame_size1,&frame_nb2,&frame_size2,&repetition_valid);
                         }
                      while ((size_remaing_to_read())&&(frame_size1!=256)&(!repetition_valid));
                      move_index(0);
                      for (i=1;i<=frame_size1;i++)
                          rle3write_non_rep(header_byte,read_byte());
                    }
               fill_block(); /* All new analysis must start at 0 in the buffer */
             }
     }
}

void help()
/* Returned parameters: None
   Action: Displays the help of the program and then stops its running
   Errors: None
*/
{ printf("This utility enables you to compress a file by using RLE type 3 method\n");
  printf("as given in 'La Video et Les Imprimantes sur PC'\n");
  printf("\nUse: codrle3 source target\n");
  printf("source: Name of the file to compress\n");
  printf("target: Name of the compressed file\n");
}

int main(argc,argv)
/* Returned parameters: Return an error code (0=None)
   Action: Main procedure
   Errors: Detected, handled and an error code is returned, if any
*/
int argc;
char *argv[];
{ if (argc!=3)
     { help();
       exit(BAD_ARGUMENT);
     }
  else if ((source_file=fopen(argv[1],"rb"))==NULL)
          { help();
            exit(BAD_FILE_NAME);
          }
       else if ((dest_file=fopen(argv[2],"wb"))==NULL)
               { help();
                 exit(BAD_FILE_NAME);
               }
            else { rle3encoding();
                   fclose(source_file);
                   fclose(dest_file);
                 }
  printf("Execution of codrle3 completed.\n");
  return (NO_ERROR);
}
